﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace FreeDream.ConsoleApp
{
    public  class DemoTest01
    {
        public static void test(int num)
        {
            #region 生成随机不重复数据

            int[] intArray = new int[num];
            List<int> newArray = new List<int>();
            Random rnd = new Random();
            while (newArray.Count < num)
            {
                int tempNumber = rnd.Next(1, num + 1);
                if (!newArray.Contains(tempNumber))
                    newArray.Add(tempNumber);
            }

            #endregion

            newArray.Sort();
            int mid = newArray.Count / 2;

            List<int> list = new List<int>();
            for (int i = 0; i < newArray.Count; i++)
            {
                if (i == mid)
                {
                    if (newArray.Count % 2 == 1)
                    {
                        list.Add(newArray[i]);
                    }
                    break;
                }
                list.Add(newArray[i]);
                list.Add(newArray[newArray.Count - 1 - i]);
            }

            foreach (int i in list)
            {
                Console.WriteLine(i);
            }

        }

        public static void test2()
        {
            List<student> lst3 = new List<student>()
            {
                new  student{ id = 1,name = "01"}, new student{ id = 2,name = "02"}
            };

            var lst = new { id = 1, name = "01" };
            var lst2 = int.Parse(lst3.GetType().GetProperty("id").GetValue(lst3, null).ToString());

            var tu1 = new Tuple<int, string>(int.Parse(lst.GetType().GetProperty("id").GetValue(lst, null).ToString()),
                lst.GetType().GetProperty("name").GetValue(lst, null).ToString()).Item1;
            var tu2 = new Tuple<int, string>(int.Parse(lst.GetType().GetProperty("id").GetValue(lst, null).ToString()),
                lst.GetType().GetProperty("name").GetValue(lst, null).ToString()).Item2;

        }
        public class student
        {
            public int id { get; set; }

            public string name { get; set; }
        }

        #region 背包装物品不超过重量

        /// <summary>
        /// 背包装物品不超过重量
        /// </summary>
        /// <param name="s">总重量</param>
        public void beibao01(int s =18)
        {
            //int s = 15;
            //int wupintotal = 7; //几个物品
            int[] arr = new int[8] {0, 1, 4, 3, 4, 5, 2, 6 }; //长度：wupintotal +1
            //knap(s, 7);
            if (knap(s, arr.Length-1, arr) ==1)
            {
                Console.WriteLine($"{DateTime.Now},OK");
            }
            else
            {
                Console.WriteLine($"{DateTime.Now},NO");
            }
        }
        /// <summary>
        /// 背包装物品不超过重量
        /// </summary>
        /// <param name="s">总重量</param>
        /// <param name="n">数组下标</param>
        /// <param name="arr1">数组值</param>
        /// <returns></returns>
        private int knap(int s, int n, int[] arr1)
        {
            Console.WriteLine($"{DateTime.Now},s={s},n={n}");
            if (s == 0)
            {
                Console.WriteLine($"{DateTime.Now},.......s={s},n={n}");
                return 1;
            }
            if (s < 0 || (s > 0 && n < 1))
            {
                Console.WriteLine($"{DateTime.Now},********s={s},n={n}");
                return 0;
            }
            if (knap(s - arr1[n], n - 1,arr1) == 1)
            {
                Console.WriteLine($"{DateTime.Now}...knap......{arr1[n]},s={s},n={n}");
                return 1;
            }

            return knap(s, n - 1,arr1);
        }

        #endregion

        #region 
        //假设现有容量m kg的背包，另外有i个物品，重量分别为w[1] w[2] ... w[i] （kg）,价值分别为p[1] p[2] ... p[i] （元）,
        //将哪些物品放入背包可以使得背包的总价值最大？
        //最大价值是多少？（示例一：m=10  i=3  重量和价值分别为 3kg-4元 4kg-5元 5kg-6元  ）
        //原文链接：https://blog.csdn.net/KLZK007/article/details/130085099

        public void BeibaoTest02(int m )
        {
            //int m;
            //int n = 3;
            int[] weight = new int[4] { 0, 3, 4, 5 };
            int[] price = new int[4] { 0, 4, 5, 6 };

            Console.WriteLine(ExhaustiveMethod(m, weight, price));
        }
        
        #region 穷举法

        /// <summary>
        /// 物品放入背包最大价值
        /// </summary>
        /// <param name="m">总容量</param>
        /// <param name="w">重量</param>
        /// <param name="p">价值</param>
        /// <returns></returns>
        public static int ExhaustiveMethod(int m, int[] w, int[] p)
        {
            int i = w.Length - 1;//物品个数
            int maxPrice = 0;
            for (int j = 0; j < Math.Pow(2, i); j++)
            {
                int tempWeight = 0;
                int tempPrice = 0;
                //取得二进制值
                for (int number = 1; number <= i; number++)
                {
                    int result = GetBinarySystem(j, number);
                    if (result == 1)
                    {
                        tempWeight += w[number];
                        tempPrice += p[number];
                    }
                }
                if (tempWeight <= m && tempPrice > maxPrice)
                {
                    maxPrice = tempPrice;
                }
            }
            return maxPrice;
        }
        public static int GetBinarySystem(int j, int number)
        {
            //取得i的第number位的二进制值，是1还是0
            int A = j;
            int B = (int)Math.Pow(2, number - 1);
            int result = A & B;
            if (result == 0)
            {
                return 0;
            }
            else
            {
                return 1;
            }

        }

        #endregion


        #region 动态规划算法 递归

        public static int MaxPrice(int m, int i, int[] w, int[] p)
        {
            //int i = w.Length - 1;
            if (i == 0 || m == 0) return 0;
            if (w[i] > m)
            {
                return MaxPrice(m, i - 1, w, p);
            }
            else
            {
                int tempPrice1 = MaxPrice(m - w[i], i - 1, w, p) + p[i];
                int tempPrice2 = MaxPrice(m, i - 1, w, p);
                if (tempPrice1 > tempPrice2)
                {
                    return tempPrice1;
                }
                else
                {
                    return tempPrice2;
                }
            }
        }

        #endregion

        #region MyRegion

        /// <summary>
        /// 2.自顶向下带备忘录：
        /// </summary>
        /// <param name="m"></param>
        /// <param name="i"></param>
        /// <param name="w"></param>
        /// <param name="p"></param>
        /// <param name="momery"></param>
        /// <returns></returns>
        public static int MaxPriceA(int m, int i, int[] w, int[] p, int[,] momery)
        {
            //int i = w.Length - 1;
            if (i == 0 || m == 0) return 0;
            if (momery[m, i] != 0)
            {
                return momery[m, i];
            }
            if (w[i] > m)
            {
                momery[m, i] = MaxPriceA(m, i - 1, w, p, momery);
                return momery[m, i];
            }
            else
            {
                int tempPrice1 = MaxPriceA(m - w[i], i - 1, w, p, momery) + p[i];
                int tempPrice2 = MaxPriceA(m, i - 1, w, p, momery);
                if (tempPrice1 > tempPrice2)
                {
                    momery[m, i] = tempPrice1;
                }
                else
                {
                    momery[m, i] = tempPrice2;
                }
                return momery[m, i];
            }
        }

        /// <summary>
        /// 自底向上
        /// </summary>
        /// <param name="m"></param>
        /// <param name="i"></param>
        /// <param name="w"></param>
        /// <param name="p"></param>
        /// <param name="momery"></param>
        /// <returns></returns>
        public static int MaxPriceB(int m, int i, int[] w, int[] p, int[,] momery)
        {
            if (momery[m, i] != 0) return momery[m, i];
            for (int tempM = 1; tempM < m + 1; tempM++)
            {
                for (int tempI = 1; tempI < i + 1; tempI++)
                {
                    if (momery[tempM, tempI] != 0) continue;
                    if (w[tempI] > tempM)
                    {
                        momery[tempM, tempI] = momery[tempM, tempI - 1];
                    }
                    else
                    {
                        int maxPrice1 = momery[tempM - w[tempI], tempI - 1] + p[tempI];
                        int maxPrice2 = momery[tempM, tempI - 1];
                        if (maxPrice1 > maxPrice2)
                        {
                            momery[tempM, tempI] = maxPrice1;
                        }
                        else
                        {
                            momery[tempM, tempI] = maxPrice2;
                        }
                    }
                }
            }
            return momery[m, i];
        }

        #endregion

        #endregion

        #region 回溯方法

        public void BeibaoTest03()
        {
            List<Item> itemList = new List<Item>
            {
                new Item { Name = "item1", Weight = 1, Value = 200 },
                new Item { Name = "item2", Weight = 3, Value = 240 },
                new Item { Name = "item3", Weight = 2, Value = 140 },
                new Item { Name = "item4", Weight = 5, Value = 210 },
                new Item { Name = "item5", Weight = 4, Value = 320 },
                new Item { Name = "item6", Weight = 3, Value = 405 },
            };
            int maxWeight = 12;
            KnapsackResult r = Knapsack(itemList, maxWeight);
            Console.WriteLine($"Max Value: {r.MaxValue}");
            foreach (var item in r.OptItemList)
            {
                Console.WriteLine($"{item.Name} {item.Weight} {item.Value}");
            }
        }

        #region 回溯函数

        public class KnapsackResult
        {
            public int MaxValue { get; set; }
            public List<Item> OptItemList { get; set; }
        }

        public class Item
        {
            public string Name { get; set; }
            public int Weight { get; set; }
            public int Value { get; set; }
        }

        /// <summary>
        /// 返回容量最大价值
        /// </summary>
        /// <param name="itemList">所有物品价值</param>
        /// <param name="maxWeight">总容量</param>
        /// <returns></returns>
        public static KnapsackResult Knapsack(List<Item> itemList, int maxWeight)
        {
            KnapsackResult r = new KnapsackResult();
            List<Item> curItemList = new List<Item>();
            BackTrack(itemList, curItemList, 0, 0, 0, maxWeight, ref r);
            return r;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="itemList">物品列表</param>
        /// <param name="curItemList">当前选择列表</param>
        /// <param name="curValue">当前价值</param>
        /// <param name="curWeight">当前重量</param>
        /// <param name="curIndex">当前选择的物品项</param>
        /// <param name="maxWeight">背包最大载重</param>
        /// <param name="r">返回结果类型</param>
        private static void BackTrack(List<Item> itemList, List<Item> curItemList, int curValue, int curWeight, int curIndex, int maxWeight, ref KnapsackResult r)
        {
            //https://pythonjishu.com/azfejrrinjauhsk/
            if (curWeight > maxWeight) // 超重，不符合选择条件，直接返回
            {
                return;
            }

            if (curIndex >= itemList.Count) // 遍历完了所有的物品，比较该次选择和上次选择，保留最佳结果
            {
                if (curValue > r.MaxValue)
                {
                    r.MaxValue = curValue;
                    r.OptItemList = new List<Item>(curItemList);
                }
                return;
            }

            // 选择当前物品
            curItemList.Add(itemList[curIndex]);
            BackTrack(itemList, curItemList, curValue + itemList[curIndex].Value, curWeight + itemList[curIndex].Weight, curIndex + 1, maxWeight, ref r);
            curItemList.RemoveAt(curItemList.Count - 1);

            // 不选择当前物品
            BackTrack(itemList, curItemList, curValue, curWeight, curIndex + 1, maxWeight, ref r);
        }

        #endregion

        #region MyRegion

        public void BeibaoTest04()
        {
            //货物重量和价值
            int[,] a;
            //背包承重
            int w;
            ////测试数据1，答案是133
            //a = new int[,] { { 77, 22, 29, 50, 99 }, { 92, 22, 87, 46, 90 } };
            //w = 100;
            ////测试数据2，答案是334
            a = new int[,] { { 79, 58, 86, 11, 28, 62, 15, 68 }, { 83, 14, 54, 79, 72, 52, 48, 62 } };
            w = 200;
            int v;
            v = getmaxvalue(w, a, 0);
            Console.WriteLine($"最大价值为：{v}");
        }

        //获得背包w，装货物o，从第flag件向后考虑，能得到的最大价值
        static int getmaxvalue(int w, int[,] o, int flag)
        {
            int v, t1, t2;
            //如果是最后一件货物
            if (flag == o.GetLength(1) - 1)
            {
                if (w >= o[0, flag])
                {
                    v = o[1, flag];
                }
                else
                {
                    v = 0;
                }
            }
            //如果装得下当前货物
            else if (w >= o[0, flag])
            {
                t1 = getmaxvalue(w - o[0, flag], o, flag + 1) + o[1, flag];
                t2 = getmaxvalue(w, o, flag + 1);
                v = t1 > t2 ? t1 : t2;
            }
            //装不下当前货物的情况
            else
            {
                v = getmaxvalue(w, o, flag + 1);
            }
            return v;
        }

        #endregion

        #endregion
    }
}
